(1) Field of the Invention
This invention is directed to a system and method for the efficient selection of hypotheses used in connection with mathematical modeling of the type used when estimating the motion of physical phenomena, for example, torpedoes, via the results of an evidential reasoner, and more particularly, to a system and method for assessing models of motion through a fluid, resulting in an acoustic signal, wherein the signal traverses an uncertain path and is received by sensors with uncertain biases in the presence of noise. Accordingly, a hypothesis selection criterion for use with the Dempster-Shafer (DS) frame of evidential reasoning that is both conceptionally simple and computationally efficient, is provided.
(2) Description of Prior Art
The Dempster-Shafer (DS) theory of evidential reasoning is one of several approaches for producing inferences from uncertain information. Its appeal for application to model assessment is that it intrinsically accommodates the expression of ignorance and naturally provides a convenient framework on which a Contact Management Model Assessment problem can be structured. The basic structure for DS evidential reasoning is the frame of discernment. Denoted by .theta., the frame of discernment is a set of mutually exclusive and exhaustive hypotheses: EQU .theta.={H.sub.1 . . . H.sub.N } (1)
The power set is the set of all subsets in the frame of discernment and has EQU K=2.vertline..THETA..vertline.-1 (2)
elements, where .vertline..theta..vertline. is the cardinality of the set .theta., and the minus one accounts for the null set .o slashed. which is not considered a member of the power set in DS theory. FIG. 4 illustrates a generic power set. A basic probability assignment (bpa) is assigned to each member of the power set, A.sub.i, and represents the belief that the hypotheses of A.sub.i are true. Denoted by m(A.sub.i), the individual bpa's are bounded between zero and one, while their sum is unity. Additionally, the measures of plausibility and support for each element can also be computed. The support for A.sub.i, denoted by s(A.sub.i), is the sum of the bpa's over all the subsets of A.sub.i, i.e., ##EQU1##
where:
m=amount of bpa PA2 a.OR right.A.sub.i =&gt;summation over the entire power set PA2 .OR right.=subset or equivalent PA2 S(A.sub.i) represents the level of belief that directly supports the hypotheses of A.sub.i. The plausibility of A.sub.i, i.e. p(A.sub.i), is a measure of the lack of support in the complement of A.sub.i and is one minus the support in the complement of A.sub.i, i.e., ##EQU2##
where .andgate.=intersection
In general, support is less than or equal to plausibility and both are bounded by zero and one. The uncertainty in assigning belief to the hypotheses contained in element A.sub.i is the difference between the plausibility and support. DS theory includes Bayesian probability as a special case when all belief is distributed among the singleton sets [H.sub.1 ], [H.sub.2 ], . . . , [H.sub.N ]. If several bodies of evidence exist for a frame of discernment, the resulting beliefs can be combined using the DS combination rule, ##EQU3##
where m.sub.1 (A.sub.j) and m.sub.2 (A.sub.k) are the belief in A.sub.j and A.sub.k generated from two bodies of evidence represented in frames of discernment one and two, respectively. The term .alpha. is the renormalization constant necessary to account for belief being placed into the null intersection .O slashed. and is ##EQU4##
In both expressions, the indices j and k range over all the elements of the power set. DS combination rule is both commutative and associative. Compatibility relations, which are used to map belief in one frame of discernment to a different frame of discernment, are useful for combining belief that originates in dissimilar frames into belief in a common frame of discernment. The compatibility map defines the relationship between the elements of two frames of discernment .theta..sub.A,B where EQU .theta..sub.A,B.OR right..theta..sub.A x.theta..sub.B (7)
and the compatibility mapping is defined by EQU C.sub.A.fwdarw.B (A.sub.k)={b.sub.j.vertline.(a.sub.1,b.sub.j).epsilon..theta..sub.A,B, a.sub.i.epsilon.A.sub.k } (8)
where at least one pair (a.sub.i, b.sub.j) is specified for each of the A.sub.K in .theta..sub.A. With a network of compatibility relations, different frames of discernment can be linked together. The collection of frames of discernment and compatibility relations is called a gallery.
The prior art includes the various model selection processes, none of which are related to the Dempster-Shafer frame of evidential reasoning, which are discussed below.
U.S. Pat. No. 5,045,852 to Mitchell et al. discloses a system and method for maximizing data compression by optimizing model selection during coding of an input stream of data symbols. In the system and method, at least two models are run and compared, and the model with the best coding performance for a given-size segment or block of compressed data is selected such that only its block is used in an output data stream. The best performance is determined by 1) respectively producing comparable-size blocks of compressed data from the input stream with the use of the two, or more models and 2) selecting the model which compresses the most input data. In the preferred embodiment, respective strings of data are produced with each model from the symbol data and are coded with an adaptive arithmetic coder into the compressed data. Each block of compressed data is started by coding the decision to use the model currently being run and all models start with the arithmetic coder parameters established at the end of the preceding block. only the compressed code stream of the best model is used in the output and that code stream has in it the overhead for selection of that model. Since the decision as to which model to run is made in the compressed data domain, i.e., the best model is chosen on the basis on which model coded the most input symbols for a given-size compressed block, rather than after coding a given number of input symbols, the model selection decision overhead scales with the compressed data. Successively selected compressed blocks are combined as an output code stream to produce an output of compressed data, from input symbols, for storage or transmission. In Mitchell et al., the process disclosed always performs all the processing and chooses the best result after the processing is performed, without ranking which models produce the best results prior to processing.
U.S. Pat. No. 5,233,541 to Corwin et al. discloses an automatic target detection process. Accordingly, a data processing technique is provided for detecting, locating and identifying targets from a plurality of images generated by an imaging sensor such as an imaging lidar system. The process employs physical models of signals produced by target objects of interest. Such a model based detection system globally processes frames of data to determine the existence and location of component elements that characterize the target being modeled. Similar to Mitchell et al., the process disclosed in Corwin et al. chooses only the best result after all processing is finished instead of ranking and selecting models which could produce the best results, prior to processing. Also, the model developed by Corwin et al. is of a target's orientation in a still frame, thereby not taking into account target kinematics, environmental conditions and sensor characteristics.
The prior art discussed above relies strictly on Bayesian approaches, and unlike the present invention, it is not a selection method which is applicable to a broad range of systems such as the Bayesian system, the Dempster-Shafer system and fuzzy theory based systems, all of which have different types of uncertainties which need to be accommodated for producing the best model.
Systems related to the present invention for modeling and assessing the accuracy of assumed models of physical phenomena and which provide alternate model selections in connection with information concerning the model in the presence of noise exist in the prior art or are otherwise known. One such system and method which is in the prior art is disclosed in U.S. Pat. No. 5,373,456, assigned to the assignee of the present invention, and entitled "An Expert System for Assessing Accuracy of Models of Physical Phenomena and for Selecting Alternate Models in the Presence of Noise". This patent is incorporated into the present invention and discussed in detail in the following Detail Description of the Preferred Embodiment. Another such system and method which is known is disclosed in U.S. Pat. No. 5,581,490 entitled "Contact Management Model Assessment System for Contact Management in the Presence of Model Uncertainty and Noise", assigned to the assignee of the present invention, which also is incorporated by reference and discussed in further detail in the Detail Description of the Preferred Embodiment, below. These relevant systems suffer from the defects that they do not effectively select the most appropriate models or set of models from a plurality of models whose model state information is maintained in storage. That is, in these relevant systems, model selection, compilations of bpa (discussed above for DS evidential reasoning), support and plausibility are required for all hypothesis elements in the set of hypotheses, and all subsets of the hypotheses, placing a high computational burden on the processing capability of the system.
There exists a need, therefore, for a hypothesis selection method for modelling physical phenomena which system and method is applicable for use with the Dempster-Shafer frame of evidential reasoning as well as the Bayesian based systems and fuzzy theory based systems, and which takes into account such parameters as target kinematics, environmental conditions and sensor characteristics.